﻿//体育课共有numProject个考核项目，编号为0到numProject−1，
//考核中每两个项目被划分为一组得到分组数组groupsi，
//现规定若想完成项目groupsi[0]，必须先完成groupsi[1]。
//保证所有分组互不相同，若分组情况能顺利完成考核，请返回任意的一个完成顺序, 否则返回空数组 。
//数据范围：1≤numProject≤2000
//1≤groupsi.length≤numProject∗(numProject−1)
//
//输入：
//	3, [[2, 1]]
//返回值：
//	[1, 2, 0]
//说明：
//	要先完成1号项目，再完成2号项目，而0号项目不受约束，故可以以1 2 0的顺序完成项目。
//
//输入：
//	3, [[1, 0], [0, 1]]
//返回值：
//	[]
//说明：
//	第一个分组要求先完成0号项目，再完成1号项目；
//	而第二个分组要求先完成1号项目，再完成0号项目，自相矛盾，故不可以完成项目。

class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int> >& groups) {
        vector<vector<int>> edges(n); // 存储边
        vector<int> in(n); // ⼊度
        // 1. 建图
        for (auto v : groups) {
            int a = v[0], b = v[1]; // b -> a
            edges[b].push_back(a);
            in[a]++;
        }
        queue<int> q;
        // 2. ⼊度为 0 的点，加⼊到队列⾥⾯
        for (int i = 0; i < n; i++) {
            if (in[i] == 0) {
                q.push(i);
            }
        }
        // 3. 拓扑排序
        vector<int> ret;
        while (q.size()) {
            int a = q.front();
            q.pop();
            ret.push_back(a);
            for (auto b : edges[a]) { // a -> b
                if (--in[b] == 0) {
                    q.push(b);
                }
            }
        }
        if (ret.size() == n) return ret;
        else return {};
    }
};
